﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FindKthLargeNumber
{
    class Program
    {
        static int FindKthLarge(int[,] matrix, int k, int rowCount, int columnCount)
        {
            if (k > matrix.Length)
            {
                Console.WriteLine("Find k-th large number, k should not big than matrix's length");
                return -1;
            }
            if (rowCount* columnCount > matrix.Length || rowCount*columnCount <= 0)
            {
                Console.WriteLine("The row number and column number are incorrect");
                return -1;
            }
            Stack<int> kThStack = new Stack<int>();
            int nRowIndex = 0;
            int nCoulumIndex = 0;
          

            for (int i = rowCount - 1; i>=0; i--)
            {
                for (int n = columnCount - 1; n >= 0; n-- )
                {
                    if (0 == kThStack.Count)    //stack is empty.
                    {
                        kThStack.Push(matrix[i, n]);
                        nRowIndex = i;
                        nCoulumIndex = n;
                        continue;
                    }
                    if (kThStack.Count >= k) // Stack is full, k items in stack()
                    {
                        if (matrix[i, n] > kThStack.Last())
                        {
                            kThStack.Pop();
                            kThStack.Push(matrix[i, n]);
                            nRowIndex = i;
                            nCoulumIndex = n;
                        }
                    } 
                    else                          //Stack has free space
                    {
                        if (matrix[i, n] > kThStack.Last())
                        {
                            int topStacK = kThStack.Pop();
                            kThStack.Push(matrix[i, n]);
                            kThStack.Push(topStacK);
                            nRowIndex = i; nCoulumIndex = n;
                        }
                        else
                        {
                            kThStack.Push(matrix[i, n]);
                            nRowIndex = i; nCoulumIndex = n;
                        }

                    }

                }
            }

            if (kThStack.Count == k)
            {
                string message = string.Format("Find out the {0}-th number :{1}, row index is:{2}, column index is{3}", k, kThStack.Pop(), nRowIndex + 1, nCoulumIndex + 1);
                Console.WriteLine(message);
                return nRowIndex* nCoulumIndex;
            }

            Console.WriteLine("Can't find k-th large number");
            return -1;
        }
        static void Main(string[] args)
        {
            int[,] matrix =
            {
                {1, 2, 3},
                {4, 5, 9}, 
                {6, 8, 10}
            };
            
            //Test Cases:

            int nRet = FindKthLarge(matrix, 10, 3, 3);

            //Find 3th number;
            nRet = FindKthLarge(matrix, 3, 3, 3);
            
        }
    }
}
